# Python 2.6.4
# Project Euler, Problem 46
# Copyright 2010 Talha Zaman

from math import sqrt
def isprime(n):
    sn = sqrt(n)+1
    for i in range(2,sn+1):
        if n%i==0: return False
    return True

primes = [2]
squares = [2]
sqn = 1
i=1
done = False
while not done:
    i += 2
    if isprime(i):
        primes.append(i)
        continue
    if squares[len(squares)-1] < i:
        sqn += 1
        squares.append(2*sqn**2)
    a = len(primes)-1
    b = 0
    while 1:
        while b<len(squares) and primes[a]+squares[b]<i: b += 1
        if primes[a] + squares[b] == i:
            break
        a, b = a-1, 0
        if a<0:
            print i
            done = True
            break
